1. Field of the Invention
The present invention relates generally to an apparatus and method for transmitting and receiving data in a communication system, and in particular, to an apparatus and method of transmitting and receiving data in a communication system using Low Density Parity Check (LDPC) codes.
2. Description of the Related Art
A data transmission/reception process in a communication system can be described as follows.
The data generated from a transmission side is wireless-transmitted over a channel after undergoing source coding, channel coding, interleaving, and modulation. A reception side receives the wireless-transmitted signal, and performs demodulation, deinterleaving, channel decoding, and source decoding on the received signal.
However, the communication system may experience distortions of transmission signals due to channel noises, fading phenomenon, and Inter-Symbol Interference (ISI). Particularly, a high-speed digital communication system requiring high data throughput and reliability, such as the next generation mobile communication, digital broadcasting, and portable Internet, requires coping with the signal distortions caused by noises, fading and ISI. The channel coding and interleaving are the common technologies used for addressing the signal distortion in the high-speed digital communication system.
Interleaving minimizes a data transmission loss and increases a channel coding by dispersing damaged parts of desired transmission bits over several places without concentrating them in one location, thereby preventing burst errors that may occur frequently while the bits pass through a fading channel.
Channel coding is widely used for increasing communication reliability by allowing a reception side to detect and efficiently compensate for the signal distortion caused by noises, fading and ISI. The codes used for channel coding are known as error-correcting codes (ECC), which can correct errors. Currently, intensive research is being conducted on various types of error-correcting codes.
Well-known error-correcting codes may include block code, convolutional code, turbo code, Low Density Parity Check (LDPC) code, etc. As the present invention is related to a communication system using LDPC codes, a brief description of the LDPC code is provided below for a better understanding of the present invention.
The LDPC code is known as a code that can minimize a probability of an information loss even though it cannot guarantee complete signal transmission. That is, the LDPC code was first proposed in 1960 as a channel coding code capable of transmitting signals at a rate approximating the maximum data transfer rate (Shannon limit), which is known as the Shannon's channel coding theory. However, since the then-technological level for memories and operation processors was not adequate to realize the LDPC code, the LDPC code could not be implemented in the actual communication system. Thereafter, as the LDPC code has been rediscovered since 1996 owing to the development of the information theory and its associated technologies, active research is being conducted on a characteristic and a generation method for the LDPC code that does not noticeably increase its complexity though it uses iterative decoding. This LDPC code, together with the turbo code, has been evaluation and determined as a very excellent error-correcting code that can be used for a next generation mobile communication system, for example, the Long Term Evolution (LTE) system proposed by 3rd Generation Partnership Project (3GPP) and the Mobile Worldwide Interoperability for Microwave Access (WiMax) system proposed by Institute of Electrical and Electronics Engineers (IEEE).
The LDPC code is generally expressed using a graphical expression method, and its many characteristics can be analyzed through the methods based on graph theory, algebra and probability theory. Generally, a graph model of the channel code can draw a natural decoding algorithm because not only it is useful for code descriptions but also it can map information on coded bits to vertexes in the graph. When relations between the bits are mapped to edges in the graph, the vertexes can be regarded as communication networks that exchange predetermined messages through the edges. For example, the known decoding algorithms derived from the trellis, which can be regarded as a kind of the graph, can include a Viterbi algorithm and a Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm.
The LDPC code is generally defined as a parity check matrix, and can be expressed using a bipartite graph called a Tanner graph. The bipartite graph means that vertexes constituting the graph are divided into two different types, and the LDPC code is expressed as a bipartite graph composed of vertexes which are called “variable nodes” and “check nodes.” The variable nodes are one-to-one mapped to coded bits.
With reference to FIGS. 1 and 2, a description will now be provided of a graphical expression method for the LDPC code.
FIG. 1 is a diagram illustrating a parity check matrix H1 of an LDPC code consisting of 4 rows and 8 columns, is considered. The matrix of FIG. 1 represents an LDPC code that generates length-8 codewords as it has 8 columns. That is, the columns are mapped to 8 coded bits.
FIG. 2 is a trellis diagram for a parity check matrix H1 of an LDPC code. This is a diagram illustrating a Tanner graph corresponding to H1 of FIG. 1. Referring to FIG. 2, the Tanner graph of an LDPC code is composed of 8 variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216), and 4 check nodes 218, 220, 222 and 224. An ith column and a jth row in the parity check matrix H1 of an LDPC code are mapped to a variable node xi and a jth check node, respectively. A value of 1, i.e., non-zero value at the point where an ith column and a jth row intersect in the parity check matrix H1 of an LDPC code, means that an edge exists between the variable node xi and the jth check node in the Tanner graph as illustrated in FIG. 2.
In the Tanner graph of an LDPC code, degree of a variable node and a check node mean the number of edges connected to the nodes, and this is equal to the number of non-zero entries in a column or row mapped to the corresponding node in the parity check matrix of an LDPC code. For example, in FIG. 2, degrees of variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216) are 4, 3, 3, 3, 2, 2, 2 and 2 in sequence, respectively, and degrees of check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5 in sequence, respectively. In the columns of the parity check matrix H1 of FIG. 1, which are mapped to the variable nodes of FIG. 2, the number of non-zero entries are coincident with the degrees 4, 3, 3, 3, 2, 2, 2 and 2 in sequence, and in the rows of the parity check matrix H1 of FIG. 1, which are mapped to the check nodes of FIG. 2, the numbers of non-zero entries are coincident with the degrees 6, 5, 5 and 5 in sequence.
As described above, the coded bits are mapped one-to-one to columns of the parity check matrix, and also mapped one-to-one even to variable nodes in the Tanner graph. The degrees of the variable nodes which are mapped one-to-one to the coded bits are referred to as degrees of coded bits.
For the LDPC code, it is known that the higher-degree codeword bits are superior to the lower-degree codeword bits in decoding performance. This is due to the fact that higher-degree variable nodes can be superior in decoding performance to lower-degree variable nodes as they acquire more information through iterative decoding.
The LDPC code has been described so far. A description will now be provided of a signal constellation for the case in which the communication system employs Quadrature Amplitude Modulation (QAM) which is the commonly used high-order modulation scheme.
A QAM-modulated symbol is composed of a real part and an imaginary part, and various modulation symbols can be generated by varying sizes and signs of the real part and the imaginary part. For a better understanding of QAM characteristics, QAM will be described together with Quadrature Phase Shift Keying (QPSK) modulation.
FIG. 3A is a diagram illustrating a signal constellation of a general QPSK modulation scheme. In QPSK, two coded bits are mapped to one modulation symbol. Mapping two coded bits y0 and y1 to one modulation symbol has the following meaning. While y0 determines a sign of the real part, y1 determines a sign of the imaginary part. That is, a sign of the real part is plus (+) for y0=0, and a sign of the real part is minus (−) for y0=1. Similarly, a sign of the imaginary part is plus (+) for y1=0, and a sign of the imaginary part is minus (−) for y1=1. Since y0 and y1 are sign expression bits respectively representing signs of the real part and the imaginary part, y0 and y1 have an equal probability of error occurrence in the channel. Therefore, for QPSK modulation, the coded bits y0 and y1 mapped to one modulation symbol are equal in reliability.
FIG. 3B is a diagram illustrating a signal constellation of a general 16-QAM modulation scheme. In 16-QAM, 4 coded bits are mapped to one modulation symbol. Mapping 4 coded bits y0, y1, y2 and y3 to one modulation symbol has the following meaning. Bits y0 and y2 determine a sign and a size of the real part, respectively, and bit y1 and y3 determine a sign and a size of the imaginary part, respectively. In other words, y0 and y1 determine signs of the real part and the imaginary part of a signal, respectively, and y2 and y3 determine sizes of the real part and the imaginary part of a signal, respectively.
Generally, distinguishing a sign of a modulated signal is easier than distinguishing a size of a modulated signal. Therefore, it can be easily understood that y2 and y3 have a higher probability of error occurrence than y0 and y1, respectively. In conclusion, regarding the error-free probabilities (i.e. reliabilities) during transmission/reception of the bits, their orders are y0=y1>y2=y3. That is, QAM modulation symbol-constituting bits y0, y1, y2 and y3, unlike the QPSK modulation symbol-constituting bits, are different in reliability.
For 16-QAM modulation, among 4 bits constituting a signal, 2 bits determine signs of the real part and the imaginary part of the signal, and the other 2 bits represent sizes of the real part and the imaginary part of the signal. Therefore, it follows that the orders and roles of the bits y0, y1, y2 and y3 will be changed in accordance with a system design, as that design is different from the above.
FIG. 3C is a diagram illustrating a signal constellation of a general 64-QAM modulation scheme. In 64-QAM, 6 coded bits are mapped to one modulation symbol. Among y0, y1, y2, y3, y4 and y5 mapped to one modulation symbol, y0 and y1 determine signs of the real part and the imaginary part, respectively, and (y2, y4) and (y3, y5) determine sizes of the real part and the imaginary part, respectively.
Since distinguishing a sign of a modulated symbol is easier than distinguishing a size of a modulated symbol, y0 and y1 are higher than y2, y3, y4 and y5 in reliability. The bits y2 and y3 are determined according to whether the size of the modulated symbol is greater than or less than a value 4, and the bits y4 and y5 are determined according to whether the size of the modulated symbol is nearer to 4 or 0 from 2, or determined according to whether the size of the modulated symbol is closer to 4 or 8 from 6. Therefore, a determination range for y2 and y3 is 4, and a determination range for y4 and y5 is 2. Thus, y2 and y3 are higher than y4 and y5 in reliability. Summarizing, regarding the error-free probabilities (i.e., reliabilities) of the bits, their orders are y0=y1>y2=y3>y4=y5.
For 64-QAM modulation, among 6 bits constituting a signal, 2 bits determine signs of the real part and the imaginary part of the signal, and the other 4 bits only need to represent sizes of the real part and the imaginary part of the signal. Therefore, the orders and roles of the bits y0, y1, y2, y3, y4 and y5 can be changed according to a system design. Even for a signal constellation of 256-QAM or higher-order QAM, the roles and reliabilities of the modulation symbol-constituting bits are changed in the same manner as described above. A detailed description thereof will be omitted herein.
Conventionally, however, when the communication system using LDPC codes performs interleaving/deinterleaving, it uses an arbitrary interleaving/deinterleaving scheme regardless of the LDPC codes or the reliability characteristics of high-order modulation symbol-constituting bits, or uses an interleaving/deinterleaving scheme in which only the degrees of variable nodes or check nodes of the LDPC code are taken into consideration, making it impossible to minimize the distortion of a signal transmitted over a channel.
In addition, the use of the conventional high-order modulation maps the interleaved coded bits to the modulation symbol-constituting bits without taking into account the difference in reliability characteristics between the modulation symbol-constituting bits, thereby making it impossible to minimize the distortion of a signal transmitted over a channel.